package com.fyl.basic_algorithm.dynamic_programming;

/**
 * @Description:
 * @author:fyl
 * @date 2021/4/20 23:28
 * @Modified By:
 * @Modified Date:
 */
public class SpellCorr {
    private char[] a = "mitcmu".toCharArray();
    private char[] b = "mtacnu".toCharArray();
    private int n = 6;
    private int m = 6;
    private int minDist = Integer.MAX_VALUE;  //储存结果

    /**
     * 调用方式lwstBT(0,0,0)
     * 莱文斯坦距离
     * @param i     a字符串的指针
     * @param j     b字符串的指针
     * @param edist 编辑长度
     */
    public void lwstBT(int i, int j, int edist) {
        if (i == n || j == m) {
            if (i < n) edist += (n - i);
            if (j < m) edist += (m - j);
            if (edist < minDist) minDist = edist;
            return;
        }

        if (a[i] == b[j]) { //两个字符匹配
            lwstBT(i + 1, j + 1, edist);
        } else { //两个字符匹配
            lwstBT(i + 1, j, edist + 1); //删除a[i]或者b[i]前添加一个字符
            lwstBT(i, j + 1, edist + 1);  //删除b[i]或者a[i]前添加一个字符
            lwstBT(i + 1, j + 1, edist + 1); //将a[i]和b[i]替换为相同字符
        }
    }

    /**
     * 动态规划状态转移表法
     *
     * @param a 字符串
     * @param n a字符串的长度
     * @param b 字符串
     * @param m b字符串的长度
     * @return 两个字符串的莱文斯坦距离
     */
    public int lwstDP(char[] a, int n, char[] b, int m) {
        int[][] minDist = new int[n][m]; //状态表
        for (int i = 0; i < m; i++) {  //初始化第0行:a[0..0]与b[0..i]的编辑距离
            if (a[0] == b[i]) minDist[0][i] = i;
            else if (i != 0) minDist[0][i] = minDist[0][i - 1] + 1;
            else minDist[0][i] = 1;
        }
        for (int i = 0; i < n; i++) {  //初始化第0列:a[0..i]与b[0..0]的编辑距离
            if (a[i] == b[0]) minDist[i][0] = i;
            else if (i != 0) minDist[i][0] = minDist[i - 1][0] + 1;
            else minDist[i][0] = 1;
        }

        for (int i = 0; i < n; i++) {  //填表
            for (int j = 0; j < m; j++) {
                if (a[i] == b[j])
                    minDist[i][j] = min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1]);
                else minDist[i][j] = min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1] + 1);
            }
        }
        return minDist[n - 1][m - 1];
    }

    /**
     * 动态规划状态表法解决最长公共子串
     * @param a 字符串
     * @param n a字符串的长度
     * @param b 字符串
     * @param m b字符串的长度
     * @return  最长公共子串长度
     */
    public int lcs(char[] a, int n, char[] b, int m) {
        int[][] maxlcs = new int[n][m];
        for (int i = 0; i < m; i++) {
            if (a[0] == b[i]) maxlcs[0][i] = 1;
            else if (i != 0) maxlcs[0][i] = maxlcs[0][i - 1];
            else maxlcs[0][i] = 0;
        }
        for (int i = 0; i < n; i++) {
            if (a[i] == b[0]) maxlcs[i][0] = 1;
            else if (i != 0) maxlcs[i][0] = maxlcs[i - 1][0];
            else maxlcs[i][0] = 0;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i] == b[j]) maxlcs[i][j] = min(maxlcs[i - 1][j], maxlcs[i][j - 1], maxlcs[i - 1][j - 1] + 1);
                else maxlcs[i][j] = min(maxlcs[i - 1][j], maxlcs[i][j - 1], maxlcs[i - 1][j - 1]);
            }
        }
        return maxlcs[n - 1][m - 1];
    }

    private int min(int x, int y, int z) {
        int minv = Integer.MAX_VALUE;
        if (x < minv) minv = x;
        if (y < minv) minv = y;
        if (z < minv) minv = z;
        return minv;
    }
}
